The format ordinarily used in television is termed the “interlaced video” format. The interlace video format is based upon a successive sequence of even lines followed by odd lines of an image. More specifically images are constructed from successive frames (half images) comprising frames having even pixel lines of a given image that are interlaced, i.e., alternated, with frames having only odd pixel lines of a following image. This halving of the amount of information in an interlace video format has the detrimental effect of reducing the quality of the images, and this is all the more noticeable when moving images are involved. Specifically, the image represented by a first frame is not quite the same as that represented by the following frame, since they are separated by an interval of time and the objects represented are in motion. The simple superposition of two successive frames therefore does not make it possible to reconstruct an image on the basis of a sequence of images in the interlaced video format. This simple superposition is possible only when the sequence of images is in the so-called film format (also known as “movie” format), for which each filmed image has been decomposed over two frames during encoding to the interlaced format.
FIGS. 1A and 1B represent two examples of successive frames. A frame (m−1) of the first type, represented partially in FIG. 1A, precedes in time a frame m of the second type, represented partially in FIG. 1B. Frame (m−1) of a first type and frame m of a second type are respectively associated with two successive images.
Each frame comprises columns, indexed by the letter k, and lines, indexed by the letter n. Each frame comprises only half the pixels of the associated image. Frame (m−1) of the first type, for example even, comprises only lines of pixels of a first type, for example even lines (lines 2n), where n is an integer. Frame m of a second type, for example odd, comprises only lines of pixels of a second type, for example odd lines (lines (2n+1)). The missing lines of an even frame are the odd lines, and vice versa. The lines present in an even frame are the even lines, and vice versa.
There exist numerous methods of converting the “interlaced” display format to the natural format termed “progressive” or “sequential” where the totality of the lines is coded for each image. This conversion is known by the name deinterlacing. The goal is to reconstruct on the basis of a sequence of interlaced source images a sequence of progressive images of visual quality that is as close as possible to the sequence of source images before interlacing.
The conversion of the interlaced format to the progressive format necessitates interpolating the missing lines for each frame, that is to say the even lines for the odd frames and the odd lines for the even frames. The reconstruction of the pixels of the missing lines must make it possible to obtain a sequence of images of the best possible quality.
The interpolation of the missing lines of a given frame can be performed on the basis of the lines present in this frame: we will speak of spatial interpolation. For example, the value of the pixel Pk,2n,m situated in column k and in line 2n of frame m represented in FIG. 1B can be calculated on the basis of the values of the pixels of the line above (2n−1) and of the line below (2n+1) in frame m.
The interpolation can also be temporal, that is to say the values of the pixels of a previous frame and/or of a following frame can be used to evaluate the values of the pixels of the missing lines of a given frame. A purely temporal interpolation is for example used when the image sequence is in the “movie” format. For example, the value of the pixel Pk,2n,m situated in column k and in line 2n of frame m represented in FIG. 1B can be chosen to be equal to the value of the pixel Pk,2n,m−1 situated in column k and in line 2n of frame (m−1) represented in FIG. 1A.
An interpolation method can also comprise a spatio-temporal interpolation, that is to say the evaluation of the value of a pixel of a missing line of a given frame is performed on the basis of the values of the pixels of lines present in the given frame, on the one hand, and on the basis of the values of the pixels of a previous frame and/or of a following frame on the other hand. Among the spatio-temporal methods of interpolation may be cited by way of example median filtering.
Interpolation methods can also comprise methods with motion compensation.
Spatial interpolation is widely used, in particular in methods of spatial or spatio-temporal interpolation.
A relatively simple method of spatial interpolation consists in choosing as value of a pixel Pk,2n,m of a column k and of a line 2n a mean of the values of the pixels Pk,2n−1,m and Pk,2n+1,m belonging to the same column k and to the lines present (2n−1) and (2n+1) which flank the missing line 2n. The interpolation is performed in a vertical direction. However, when the image associated with frame m represents shapes with diagonal contours, a vertical interpolation is at risk of leading to the appearance of staircasing at the level of the diagonal contours.
In order to remedy this drawback, it is known to perform a diagonal interpolation. FIG. 2 represents an example of a diagonal interpolation algorithm for the evaluation of the value of a given pixel Pk,2n,m of a missing line 2n of a frame m. A direction of interpolation is estimated (step 21), conventionally by calculating a score for each direction Di indexed by the letter i of a set of directions (step 23) and by choosing the direction D_min for which the associated score is the lowest as direction of interpolation. The algorithm also comprises an interpolation step (step 22) based on the values of the pixels aligned along the direction of interpolation to evaluate the value Y*(2n,k) of the pixel Pk,2n,m.
European Patent EP 1 450 560 describes an exemplary algorithm for searching for the best direction. The search is performed within a window of ten pixels around the pixel whose value is to be evaluated. This window is referenced 1 in FIG. 1B. Seven directions are considered and indexed by the letter i, where i varies between 0 and 6:
a direction substantially at −63° relative to a vertical direction, and in the trigonometric sense, for which i=0,
a direction substantially at −45°, for which i=1,
a direction substantially at −26°, for which i=2,
the vertical direction, for which i=3,
a direction substantially at 26°, for which i=4,
a direction substantially at 45°, for which i=5, and
a direction substantially at 63°, for which i=6.
For each direction considered, there is calculated a weighted sum of the absolute differences of the values of pixels (“Sum of Absolute Differences” or SAD).
To return to the frame example illustrated by FIG. 1B, for the vertical direction (i.e. for i=3), the weighted sum SAD(3) can be calculated using the formula:
            SAD      ⁡              (        3        )              =                  0.125        *                                                      Y              ⁡                              (                                                                            2                      ⁢                      n                                        -                    1                                    ,                                      k                    -                    1                                                  )                                      -                          Y              ⁡                              (                                                                            2                      ⁢                      n                                        +                    1                                    ,                                      k                    -                    1                                                  )                                                                  +              0.75        *                                                      Y              ⁡                              (                                                                            2                      ⁢                      n                                        -                    1                                    ,                  k                                )                                      -                          Y              ⁡                              (                                                                            2                      ⁢                      n                                        +                    1                                    ,                  k                                )                                                                  +              0.125        *                                                      Y              ⁡                              (                                                                            2                      ⁢                      n                                        -                    1                                    ,                                      k                    +                    1                                                  )                                      -                          Y              ⁡                              (                                                                            2                      ⁢                      n                                        +                    1                                    ,                                      k                    +                    1                                                  )                                                                    ,
where Y(2n, k) designates the value of the pixel Pk,2n,m.
For a direction at +45° in the trigonometric sense and relative to the vertical direction, (i.e. i=5), the weighted sum SAD(5) can be calculated using the formula:
      SAD    ⁡          (      5      )        =            0.3125      *                                            Y            ⁡                          (                                                                    2                    ⁢                    n                                    -                  1                                ,                                  k                  -                  2                                            )                                -                      Y            ⁡                          (                                                                    2                    ⁢                    n                                    +                  1                                ,                k                            )                                                    +          0.375      *                                            Y            ⁡                          (                                                                    2                    ⁢                    n                                    -                  1                                ,                                  k                  -                  1                                            )                                -                      Y            ⁡                          (                                                                    2                    ⁢                    n                                    +                  1                                ,                                  k                  +                  1                                            )                                                    +          0.3125      *                                                            Y              ⁡                              (                                                                            2                      ⁢                      n                                        -                    1                                    ,                  k                                )                                      -                          Y              ⁡                              (                                                                            2                      ⁢                      n                                        +                    1                                    ,                                      k                    +                    2                                                  )                                                              .            
For a given direction, each difference is in fact computed between two pixels aligned along this direction. By choosing the lowest weighted sum, from among the weighted sums SAD(i) calculated, it is possible to estimate the direction for which the modifications of values of the pixels between the line above and the line below are minimal, that is to say the direction of the contour at the level of this pixel.
Such an algorithm can for example be applied to search for the direction of interpolation corresponding to the pixel Pk,2n,m of the frame represented in FIG. 1B. For the sake of simplification, we consider that the pixels represented in this frame can take only two values, corresponding for example to the color black and to the color white. This algorithm leads to selecting the direction at 45°, represented by a double arrow in FIG. 1B.
Once the direction of interpolation has been thus estimated for a given pixel, the value of this pixel can be interpolated with the aid of the values of the pixels aligned along this direction, here the pixels Pk−1,2n−1,m and Pk+1,2n+1,m. In this simplified example, the evaluated value of the pixel Pk,2n,m corresponds to the color black.
However, algorithms for searching for the direction of interpolation can lead to an indeterminacy or to a wrong result, in particular for images exhibiting objects of relatively small thickness.
FIG. 3 illustrates an exemplary odd frame associated with an image representing an object of relatively small thickness. The thickness of the object, whose contours are represented by dashed lines, is of course relative to the number of pixels.
The algorithm described in European Patent EP 1 450 560 leads to selecting the direction D0, associated with an angle of about −63° relative to the vertical direction of the columns, as direction of interpolation corresponding to the pixel Pk,2n,m. The weighted sums SAD(1) and SAD(5) associated with the directions D1 and D5, respectively −45° and +45° relative to the vertical direction, are also relatively small.
Other known algorithms for searching for the direction of interpolation can also culminate in a wrong result, or else in an indeterminacy between mutually very different directions.
Accordingly, what is needed is a method and an apparatus to determine the direction of interpolation with greater reliability.